
//542.01 矩阵
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        //多源BFS,从0开始向外进行扩展
        int n=mat.size(),m=mat[0].size();
        int dx[]={0,0,-1,1};
        int dy[]={1,-1,0,0};
        queue<pair<int,int>> q;
        for(int i=0;i<n;i++)   //记录所有0位置
        for(int j=0;j<m;j++)
        if(mat[i][j]==0) q.push({i,j});

        //进行BFS
        int step=0;
        vector<vector<int>> ret(n,vector<int>(m));
        while(!q.empty())   //进行BFS
        {
            int _size=q.size();
            step++;
            for(int i=0;i<_size;i++)
            {
                int x=q.front().first,y=q.front().second;
                q.pop();
                for(int k=0;k<4;k++)
                {   
                    int a=x+dx[k],b=y+dy[k];
                    if(a>=0&&a<n&&b>=0&&b<m&&mat[a][b]&&!ret[a][b])
                    {
                        ret[a][b]=step;  //对该位置答案进行更新
                        q.push({a,b});
                    }
                }   
            }
        }
        return ret;
    }
};